<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <h2>一、是什么</h2>
  <div>diff 算法是一种通过同层的树节点进行比较的高效算法</div>
  <br>
  <div>其有两个特点：</div>
  <ul>
    <li>比较只会在同层级进行, 不会跨层级比较</li>
    <li>在diff比较的过程中，循环从两边向中间比较</li>
    <li>diff 算法的在很多场景下都有应用，在 vue 中，作用于虚拟 dom 渲染成真实 dom 的新旧 VNode 节点比较</li>
  </ul>
  <h2>二、比较方式</h2>
  <div>diff整体策略为：深度优先，同层比较</div>
  <ul>
    <li>比较只会在同层级进行, 不会跨层级比较</li>
    <li>比较的过程中，循环从两边向中间收拢</li>
  </ul>
  <h2>三、原理分析</h2>
  <div>当数据发生改变时，set方法会调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的DOM打补丁，更新相应的视图</div>
  <script>
    // function patch(oldVnode, vnode, hydrating, removeOnly) {
    //     if (isUndef(vnode)) { // 没有新节点，直接执行destory钩子函数
    //         if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
    //         return
    //     }

    //     let isInitialPatch = false
    //     const insertedVnodeQueue = []

    //     if (isUndef(oldVnode)) {
    //         isInitialPatch = true
    //         createElm(vnode, insertedVnodeQueue) // 没有旧节点，直接用新节点生成dom元素
    //     } else {
    //         const isRealElement = isDef(oldVnode.nodeType)
    //         if (!isRealElement && sameVnode(oldVnode, vnode)) {
    //             // 判断旧节点和新节点自身一样，一致执行patchVnode
    //             patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
    //         } else {
    //             // 否则直接销毁及旧节点，根据新节点生成dom元素
    //             if (isRealElement) {

    //                 if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
    //                     oldVnode.removeAttribute(SSR_ATTR)
    //                     hydrating = true
    //                 }
    //                 if (isTrue(hydrating)) {
    //                     if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
    //                         invokeInsertHook(vnode, insertedVnodeQueue, true)
    //                         return oldVnode
    //                     }
    //                 }
    //                 oldVnode = emptyNodeAt(oldVnode)
    //             }
    //             return vnode.elm
    //         }
    //     }
    // }
  </script>
  <br>
  <div>patch函数前两个参数位为oldVnode 和 Vnode ，分别代表新的节点和之前的旧节点，主要做了四个判断：</div>
  <ul>
    <li>没有新节点，直接触发旧节点的destory钩子</li>
    <li>没有旧节点，说明是页面刚开始初始化的时候，此时，根本不需要比较了，直接全是新建，所以只调用 createElm</li>
    <li>旧节点和新节点自身一样，通过 sameVnode 判断节点是否一样，一样时，直接调用 patchVnode去处理这两个节点</li>
    <li>旧节点和新节点自身不一样，当两个节点不一样的时候，直接创建新节点，删除旧节点</li>
  </ul>
  <script>
    // function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
      //   // 如果新旧节点一致，什么都不做
      //   if (oldVnode === vnode) {
      //     return
      //   }

      //   // 让vnode.el引用到现在的真实dom，当el修改时，vnode.el会同步变化
      //   const elm = vnode.elm = oldVnode.elm

      //   // 异步占位符
      //   if (isTrue(oldVnode.isAsyncPlaceholder)) {
      //     if (isDef(vnode.asyncFactory.resolved)) {
      //       hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
      //     } else {
      //       vnode.isAsyncPlaceholder = true
      //     }
      //     return
      //   }
      //   // 如果新旧都是静态节点，并且具有相同的key
      //   // 当vnode是克隆节点或是v-once指令控制的节点时，只需要把oldVnode.elm和oldVnode.child都复制到vnode上
      //   // 也不用再有其他操作
      //   if (isTrue(vnode.isStatic) &&
      //     isTrue(oldVnode.isStatic) &&
      //     vnode.key === oldVnode.key &&
      //     (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
      //   ) {
      //     vnode.componentInstance = oldVnode.componentInstance
      //     return
      //   }

      //   let i
      //   const data = vnode.data
      //   if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      //     i(oldVnode, vnode)
      //   }

      //   const oldCh = oldVnode.children
      //   const ch = vnode.children
      //   if (isDef(data) && isPatchable(vnode)) {
      //     for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
      //     if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
      //   }
      //   // 如果vnode不是文本节点或者注释节点
      //   if (isUndef(vnode.text)) {
      //     // 并且都有子节点
      //     if (isDef(oldCh) && isDef(ch)) {
      //       // 并且子节点不完全一致，则调用updateChildren
      //       if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)

      //       // 如果只有新的vnode有子节点
      //     } else if (isDef(ch)) {
      //       if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
      //       // elm已经引用了老的dom节点，在老的dom节点上添加子节点
      //       addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)

      //       // 如果新vnode没有子节点，而vnode有子节点，直接删除老的oldCh
      //     } else if (isDef(oldCh)) {
      //       removeVnodes(elm, oldCh, 0, oldCh.length - 1)

      //       // 如果老节点是文本节点
      //     } else if (isDef(oldVnode.text)) {
      //       nodeOps.setTextContent(elm, '')
      //     }

      //     // 如果新vnode和老vnode是文本节点或注释节点
      //     // 但是vnode.text != oldVnode.text时，只需要更新vnode.elm的文本内容就可以
      //   } else if (oldVnode.text !== vnode.text) {
      //     nodeOps.setTextContent(elm, vnode.text)
      //   }
      //   if (isDef(data)) {
      //     if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
      //   }
      // }
  </script>
  <div>patchVnode主要做了几个判断：</div>
  <ul>
    <li>新节点是否是文本节点，如果是，则直接更新dom的文本内容为新节点的文本内容</li>
    <li>新节点和旧节点如果都有子节点，则处理比较更新子节点</li>
    <li>只有新节点有子节点，旧节点没有，那么不用比较了，所有节点都是全新的，所以直接全部新建就好了，新建是指创建出所有新DOM，并且添加进父节点</li>
    <li>只有旧节点有子节点而新节点没有，说明更新后的页面，旧节点全部都不见了，那么要做的，就是把所有的旧节点删除，也就是直接把DOM 删除</li>
  </ul>
  <script>
    // 子节点不完全一致，则调用updateChildren
    // function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
        // let oldStartIdx = 0 // 旧头索引
        // let newStartIdx = 0 // 新头索引
        // let oldEndIdx = oldCh.length - 1 // 旧尾索引
        // let newEndIdx = newCh.length - 1 // 新尾索引
        // let oldStartVnode = oldCh[0] // oldVnode的第一个child
        // let oldEndVnode = oldCh[oldEndIdx] // oldVnode的最后一个child
        // let newStartVnode = newCh[0] // newVnode的第一个child
        // let newEndVnode = newCh[newEndIdx] // newVnode的最后一个child
        // let oldKeyToIdx, idxInOld, vnodeToMove, refElm

        // // removeOnly is a special flag used only by <transition-group>
        // // to ensure removed elements stay in correct relative positions
        // // during leaving transitions
        // const canMove = !removeOnly

        // // 如果oldStartVnode和oldEndVnode重合，并且新的也都重合了，证明diff完了，循环结束
        // while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        //   // 如果oldVnode的第一个child不存在
        //   if (isUndef(oldStartVnode)) {
        //     // oldStart索引右移
        //     oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left

        //   // 如果oldVnode的最后一个child不存在
        //   } else if (isUndef(oldEndVnode)) {
        //     // oldEnd索引左移
        //     oldEndVnode = oldCh[--oldEndIdx]

        //   // oldStartVnode和newStartVnode是同一个节点
        //   } else if (sameVnode(oldStartVnode, newStartVnode)) {
        //     // patch oldStartVnode和newStartVnode， 索引左移，继续循环
        //     patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        //     oldStartVnode = oldCh[++oldStartIdx]
        //     newStartVnode = newCh[++newStartIdx]

        //   // oldEndVnode和newEndVnode是同一个节点
        //   } else if (sameVnode(oldEndVnode, newEndVnode)) {
        //     // patch oldEndVnode和newEndVnode，索引右移，继续循环
        //     patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        //     oldEndVnode = oldCh[--oldEndIdx]
        //     newEndVnode = newCh[--newEndIdx]

        //   // oldStartVnode和newEndVnode是同一个节点
        //   } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        //     // patch oldStartVnode和newEndVnode
        //     patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        //     // 如果removeOnly是false，则将oldStartVnode.eml移动到oldEndVnode.elm之后
        //     canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        //     // oldStart索引右移，newEnd索引左移
        //     oldStartVnode = oldCh[++oldStartIdx]
        //     newEndVnode = newCh[--newEndIdx]

        //   // 如果oldEndVnode和newStartVnode是同一个节点
        //   } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        //     // patch oldEndVnode和newStartVnode
        //     patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
        //     // 如果removeOnly是false，则将oldEndVnode.elm移动到oldStartVnode.elm之前
        //     canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        //     // oldEnd索引左移，newStart索引右移
        //     oldEndVnode = oldCh[--oldEndIdx]
        //     newStartVnode = newCh[++newStartIdx]

        //   // 如果都不匹配
        //   } else {
        //     if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)

        //     // 尝试在oldChildren中寻找和newStartVnode的具有相同的key的Vnode
        //     idxInOld = isDef(newStartVnode.key)
        //       ? oldKeyToIdx[newStartVnode.key]
        //       : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)

        //     // 如果未找到，说明newStartVnode是一个新的节点
        //     if (isUndef(idxInOld)) { // New element
        //       // 创建一个新Vnode
        //       createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)

        //     // 如果找到了和newStartVnodej具有相同的key的Vnode，叫vnodeToMove
        //     } else {
        //       vnodeToMove = oldCh[idxInOld]
        //       /* istanbul ignore if */
        //       if (process.env.NODE_ENV !== 'production' && !vnodeToMove) {
        //         warn(
        //           'It seems there are duplicate keys that is causing an update error. ' +
        //           'Make sure each v-for item has a unique key.'
        //         )
        //       }

        //       // 比较两个具有相同的key的新节点是否是同一个节点
        //       //不设key，newCh和oldCh只会进行头尾两端的相互比较，设key后，除了头尾两端的比较外，还会从用key生成的对象oldKeyToIdx中查找匹配的节点，所以为节点设置key可以更高效的利用dom。
        //       if (sameVnode(vnodeToMove, newStartVnode)) {
        //         // patch vnodeToMove和newStartVnode
        //         patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
        //         // 清除
        //         oldCh[idxInOld] = undefined
        //         // 如果removeOnly是false，则将找到的和newStartVnodej具有相同的key的Vnode，叫vnodeToMove.elm
        //         // 移动到oldStartVnode.elm之前
        //         canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)

        //       // 如果key相同，但是节点不相同，则创建一个新的节点
        //       } else {
        //         // same key but different element. treat as new element
        //         createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
        //       }
        //     }

        //     // 右移
        //     newStartVnode = newCh[++newStartIdx]
        //   }
        // }
  </script>

  <div>while循环主要处理了以下五种情景：</div>
  <ul>
    <li>当新老 VNode 节点的 start 相同时，直接 patchVnode ，同时新老 VNode 节点的开始索引都加 1</li>
    <li>当新老 VNode 节点的 end相同时，同样直接 patchVnode ，同时新老 VNode 节点的结束索引都减 1</li>
    <li>当老 VNode 节点的 start 和新 VNode 节点的 end 相同时，这时候在 patchVnode 后，还需要将当前真实 dom 节点移动到 oldEndVnode 的后面，同时老 VNode 节点开始索引加 1，新 VNode 节点的结束索引减 1</li>
    <li>当老 VNode 节点的 end 和新 VNode 节点的 start 相同时，这时候在 patchVnode 后，还需要将当前真实 dom 节点移动到 oldStartVnode 的前面，同时老 VNode 节点结束索引减 1，新 VNode 节点的开始索引加 1</li>
    <li>如果都不满足以上四种情形，那说明没有相同的节点可以复用，则会分为以下两种情况：</li>
    <ul>
      <li>从旧的 VNode 为 key 值，对应 index 序列为 value 值的哈希表中找到与 newStartVnode 一致 key 的旧的 VNode 节点，再进行patchVnode，同时将这个真实 dom移动到 oldStartVnode 对应的真实 dom 的前面</li>
      <li>调用 createElm 创建一个新的 dom 节点放到当前 newStartIdx 的位置</li>
    </ul>
  </ul>
  <h2>小结</h2>
  <ul>
    <li>当数据发生改变时，订阅者watcher就会调用patch给真实的DOM打补丁</li>
    <li>通过isSameVnode进行判断，相同则调用patchVnode方法</li>
    <li>patchVnode做了以下操作：</li>
    <ul>
      <li>找到对应的真实dom，称为el</li>
      <li>如果都有都有文本节点且不相等，将el文本节点设置为Vnode的文本节点</li>
      <li>如果oldVnode有子节点而VNode没有，则删除el子节点</li>
      <li>如果oldVnode没有子节点而VNode有，则将VNode的子节点真实化后添加到el</li>
      <li>如果两者都有子节点，则执行updateChildren函数比较子节点</li>
    </ul>
    <li>updateChildren主要做了以下操作：</li>
    <ul>
      <li>设置新旧VNode的头尾指针</li>
      <li>新旧头尾指针进行比较，循环向中间靠拢，根据情况调用patchVnode进行patch重复流程、调用createElem创建一个新节点，从哈希表寻找 key一致的VNode 节点再分情况操作</li>
    </ul>
  </ul>
</body>
</html>